﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace StringMatch.MatchAlgorithms
{
    public static class Rabin_Karp
    {

        /// <summary>
        /// Produces a list of indexes marking each occurrence of the pattern in the text using the Rabin-Karp algorithm
        /// </summary>
        /// <param name="pattern"></param>
        /// <param name="text"></param>
        /// <returns></returns>
        public static List<int> Match(string pattern, string text)
        {
            List<int> result = new List<int>();
            string substring = text.Substring(0, pattern.Length);
            ulong pHash = Hash(pattern);
            ulong tHash = Hash(substring);

            for (int i = 0; i < text.Length - pattern.Length; i++)
            {
                //Check if the hashes match
                if (pHash == tHash)
                    //if so verify it wasn't a collision
                    if (pattern == substring)
                        result.Add(i);

                tHash = Hash(text.Substring(i+1, pattern.Length), text[i], tHash);
                substring = text.Substring(i+1, pattern.Length);
            }

            return result;
        }
        
        /// <summary>
        /// This hash function converts the string to its base 457 equivalent. See http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm#Hash_function_used. WRONG, base 457 causes overflow even with ulong. Using base 71 instead
        /// </summary>
        /// <param name="value"></param>
        /// <returns></returns>
        private static ulong Hash(string value, char? previous = null, ulong? previousHash = null)
        {
            ulong result = 0;
            int place = value.Length-1;
            uint hashingPrime = 71;

            //if the previous character and hash are present then use those to "roll" the hash
            if (previous != null && previousHash != null)
            {
                //subtract the value of the first character of the previous hash
                previousHash -= previous * (ulong)Math.Pow(hashingPrime, place);

                //multiply the previous hash by the hash prime to move everything over a space (like multiplying a base 10 number by 10)
                previousHash *= hashingPrime;

                //add the base of the last character in the string to create the new hash
                previousHash += value[place];

                return (ulong)previousHash;
            }

            //Convert
            for (int i = 0; i < value.Length; i++)
            {  
                //multiple each character by 457^n where n is the place of the character in the resulting base 457 number
                result += value[i] * (ulong)Math.Pow(hashingPrime, place);
                place--;
            }
            return result;
        }
    }
}
